#include <iostream>

using namespace std;

template <typename T>
struct TreeNode {
	T data;
	TreeNode<T>* leftChild;
	TreeNode<T>* rightChild;

	TreeNode(T d):data(d),leftChild(nullptr),rightChild(nullptr) {
	}
};

template <typename T>
class BinaryTree {
	public:
		BinaryTree():head(NULL) {
		}
		void initTree(const T *data, const int size, const T voidValue);
		
		void midPrint();
		
		int getDepth();
	private:
		TreeNode<T> *head;
		TreeNode<T> *createTree(const T *data,const int size,int index, const T voidValue);
		void print(TreeNode<T> *root);
};

template <typename T>
void BinaryTree<T>::initTree(const T *data,const int size, const T voidValue) {
	head = createTree(data,size,0,voidValue);
}

template <typename T>
TreeNode<T> * BinaryTree<T>::createTree(const T *data,const int size,int index, const T voidValue) {
	TreeNode<T> * root = nullptr;
	if (index < size && data[index] != voidValue) {
		root = new TreeNode<T>(data[index]);
		cout<<(data[index])<<endl;
		root->leftChild = createTree(data, size, index*2+1, voidValue);
		root->rightChild = createTree(data, size, index*2+2, voidValue);
	}
	return root;
}

template <typename T>
void BinaryTree<T>::midPrint()
{
	TreeNode<T> * root = head;
	print(root);	    
}

template <typename T>
void BinaryTree<T>::print(TreeNode<T> *root)
{
	if(root->leftChild != nullptr)
	    print(root->leftChild);
	if(root != nullptr)
	    cout<<root->data<<" ";
	if(root->rightChild != nullptr)
	    print(root->rightChild);
}

template <typename T>
int BinaryTree<T>::getDepth()
{
	
}
int main() {
	int arr[] = {1,2,3,4,0,5,6,7,0,0,0,8,9,0,10,0,0,0,0,0,111};
	int size = 21;
	BinaryTree<int> bt;
	bt.initTree(arr,size,0);
	bt.midPrint(); 
	return 0;
}
